package com.markpim.algo;

public class Apl {

	private static final int SHORT_ARRAY_LENGTH = 1000;
	private static final int LONG_ARRAY_LENGTH = 10000;
	
	private static final boolean SHOW_OUTPUT = false;

	private static long startTime;

	public static void main(String[] args) {
		int[] shortArray = new int[SHORT_ARRAY_LENGTH];
		int[] longArray = new int[LONG_ARRAY_LENGTH];

		for (int i = 0; i < shortArray.length; i++) {
			shortArray[i] = (int) (Math.random() * shortArray.length);
		}
		for (int i = 0; i < longArray.length; i++) {
			longArray[i] = (int) (Math.random() * longArray.length);
		}

		printSortingStats(shortArray, "Short array input", 0);

		printSortingStats(longArray, "Long array input", 0);

		insertionSort(shortArray);
		insertionSort(longArray);
		mergeSort(shortArray);
		mergeSort(longArray);
		quickSort(shortArray);
		quickSort(longArray);
	}

	private static void insertionSort(int[] numbers) {
		startTime = System.currentTimeMillis();
		for (int i = 0; i < numbers.length; i++) {
			int temp = numbers[i];
			int j = i;
			while (j > 0 && numbers[j - 1] >= temp) {
				numbers[j] = numbers[j - 1];
				j--;
			}
			numbers[j] = temp;

		}
		printSortingStats(numbers, "Insertionsort", System.currentTimeMillis()
				- startTime);
	}

	private static void mergeSort(int[] numbers) {

		startTime = System.currentTimeMillis();
		numbers = mergeSortRecursive(numbers);
		printSortingStats(numbers, "Mergesort", System.currentTimeMillis()
				- startTime);
	}

	private static int[] mergeSortRecursive(int[] numbers) {
		if (numbers.length > 1) {
			int elementsInA1 = numbers.length / 2;
			int elementsInA2 = elementsInA1;
			if ((numbers.length % 2) == 1)
				elementsInA2 += 1;
			int arr1[] = new int[elementsInA1];
			int arr2[] = new int[elementsInA2];
			for (int i = 0; i < elementsInA1; i++)
				arr1[i] = numbers[i];
			for (int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
				arr2[i - elementsInA1] = numbers[i];
			arr1 = mergeSortRecursive(arr1);
			arr2 = mergeSortRecursive(arr2);
			int i = 0, j = 0, k = 0;
			while (arr1.length != j && arr2.length != k) {
				if (arr1[j] < arr2[k]) {
					numbers[i] = arr1[j];
					i++;
					j++;
				} else {
					numbers[i] = arr2[k];
					i++;
					k++;
				}
			}
			while (arr1.length != j) {
				numbers[i] = arr1[j];
				i++;
				j++;
			}
			while (arr2.length != k) {
				numbers[i] = arr2[k];
				i++;
				k++;
			}
		}
		return numbers;
	}

	private static void quickSort(int[] numbers) {

		startTime = System.currentTimeMillis();
		int[] quickSorted = quickSortRecursive(numbers, 0, numbers.length - 1);
		printSortingStats(quickSorted, "Quicksort", System.currentTimeMillis()
				- startTime);

	}

	private static int[] quickSortRecursive(int[] numbers, int low, int high) {
		int i = low, j = high;
		// Get the pivot element from the middle of the list
		int pivot = numbers[low + (high - low) / 2];

		// Divide into two lists
		while (i <= j) {
			// If the current value from the left list is smaller then the pivot
			// element then get the next element from the left list
			while (numbers[i] < pivot) {
				i++;
			}
			// If the current value from the right list is larger then the pivot
			// element then get the next element from the right list
			while (numbers[j] > pivot) {
				j--;
			}

			// If we have found a values in the left list which is larger then
			// the pivot element and if we have found a value in the right list
			// which is smaller then the pivot element then we exchange the
			// values.
			// As we are done we can increase i and j
			if (i <= j) {
				swap(numbers, i, j);
				i++;
				j--;
			}
		}
		// Recursion
		if (low < j)
			quickSortRecursive(numbers, low, j);
		if (i < high)
			quickSortRecursive(numbers, i, high);

		return numbers;
	}

	private static int[] swap(int[] array, int i1, int i2) {
		int temp = array[i1];
		array[i1] = array[i2];
		array[i2] = temp;
		return array;
	}

	private static boolean isSorted(int[] numbers) {
		for (int i = 0; i < numbers.length - 1; i++) {
			if (numbers[i] > numbers[i + 1])
				return false;
		}
		return true;
	}

	private static void printSortingStats(int[] numbers, String algorithm,
			long time) {
		boolean sorted = isSorted(numbers);

		System.out.printf(algorithm + (sorted ? " output: " : ":"));
		if (SHOW_OUTPUT)
		for (int i = 0; i < numbers.length; i++) {
			System.out
					.printf(numbers[i] + (i == numbers.length - 1 ? "" : "-"));
		}
		System.out.println();
		System.out.println("Confirm sorted: " + sorted);
		if (sorted)
			System.out.println("Time: " + time);

		System.out.println();
	}

}
